'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-22 08:27:46
'''
'''
剑指 Offer 11. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。  

示例 1：

输入：[3,4,5,1,2]
输出：1
示例 2：

输入：[2,2,2,0,1]
输出：0

tips:有序数组，明显的二分思路。不过是找最小数组。单边比较，不要双边，双边复杂而不确定。l与r,这是m = (r+l)//2
通过nums[m]与nums[r]的比较得到。分三种情况：
1.nums[m]>nums[r], from the question, we know that the min number must be in the right part partitioned by
the media. so here the l = m+1.
2.nums[m]<nums[r], from the question, we know that the min number must be in the left part, and we couldn't
test whether the m is the min one, so we get here r = m
3.nums[m]=nums[r], this condition is complex, but we cold know that r cold replaced anyway, so r = r-1, this
part is important.
'''
from typing import List
class Solution:
    def minArray(self, numbers: List[int]) -> int:
        l = 0
        r = len(numbers)-1
        med = (l+r)//2
        while l<r:
            med = (l+r)//2
            if numbers[med]>numbers[r]:
                l = med+1
            elif numbers[med]<numbers[r]:
                r = med
            else:
                r -= 1
        return numbers[r]
if __name__ == "__main__":
    solution = Solution()
    nums = [3,4,5,1,2]
    print(solution.minArray(nums))